package com.squirrel.michale;

import java.util.HashMap;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/25 7:03 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2537 {

//    对某个子数组，如果数字num已出现 c次：那么若数字num多出现1次，这个子数组的pair数量会增加c；若数字num少出现1次，子数组的pair数量会减少c-1。
//    若子数组的pair数量已经不小于k了，那么向右移动右指针，pair的数量不可能减少，这时应该移动左指针。
    public long countGood(int[] nums, int k) {
        var cnt = new HashMap<Integer, Integer>();
        long ans = 0;
        int left = 0, pairs = 0;
        for (int x : nums) {
            pairs += cnt.getOrDefault(x, 0);
            cnt.merge(x, 1, Integer::sum); // 移入右端点
            while (pairs - cnt.get(nums[left]) + 1 >= k)
                pairs -= cnt.merge(nums[left++], -1, Integer::sum); // 移出左端点
            if (pairs >= k) ans += left + 1;
        }
        return ans;
    }

//    作者：灵茶山艾府
//    链接：https://leetcode.cn/problems/count-the-number-of-good-subarrays/solutions/2062761/shuang-zhi-zhen-by-endlesscheng-lkd9/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public long countGood1(int[] nums, int k) {
        int goodCount = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int goodPair = 0;
            for (int j = i; j <length; j++) {
                if (nums[i] == nums[j]) {
                    goodPair++;
                }
            }
            if (goodPair >= k) {
                goodCount++;
            }
        }
        return goodCount;
    }

    private long getGoodCount(int[] nums) {
        int goodCount = 0;
        int length = nums.length;
        HashMap<Integer, Integer> equalMap = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int cur = nums[i];
            if (equalMap.get(cur) == null) {
                equalMap.put(nums[i], 1);
            } else {
                equalMap.put(cur, equalMap.get(cur) + 1);
//                if ()
            }
        }
//        for (int i = 0; i < equalMap.size(); i++) {
//            equalMap.get(0)
//        }
//
//        for (Integer key : equalMap.keySet()) {
//            if (equalMap.get(key) >= 2) {
//                goodCount+= Math.
//            }
//        }

        return goodCount;
    }



    public long countGood2(int[] nums, int k) {
        int goodCount = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = length-1; j >=i; j--) {
                if (getGoodCount2(getSubarray(nums, i, j)) >= k) {
                    goodCount++;
                }
            }
        }
        return goodCount;
    }




    private int[] getSubarray(int[] nums, int i, int j) {
        int[] subArray = new int[j - i + 1];
        System.arraycopy(nums, i, subArray, 0, j - i + 1);
        return subArray;
    }

    private long getGoodCount2(int[] nums) {
        int goodCount = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                if (nums[i] == nums[j]) {
                    goodCount++;
                }
            }
        }
        return goodCount;
    }

    public static void main(String[] args) {
        LeetCode2537 leetCode2537 = new LeetCode2537();

        int[] nums = new int[]{1, 1, 1, 1, 1};
        System.out.println(leetCode2537.getGoodCount(nums));
        int k = 10;
        System.out.println(leetCode2537.countGood(nums, k));
        System.out.println(leetCode2537.countGood2(nums, k));
    }
}
